package example.动态规划.间隔;

/**
 * 打家劫舍
 * <p>
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 题目就是说，不能偷连着偷，而是隔1个偷,或是隔2个去偷 [隔3个去偷肯定会被各一个头给包括]
 * 一定是从第一个或者第二个去拿
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
 * <p>
 * 输入:[1,2,3,1]输出:4
 * 输入:[2,7,9,3,1]输出:12
 */
public class Demo1 {
    //todo--------------------首位不相连 看成单向链表-------------------------------

    // dp[i]=max(dp[i−2]+nums[i],dp[i−1])
    //边界条件为：
    //dp[0]=nums[0]  只有一间房屋，则偷窃该房屋
    //dp[1]=max(nums[0],nums[1])  只有两间房屋，选择其中金额较高的房屋进行偷窃
    //三间房的话可以拆分出2+1

    /**
     * 递归一般都存在重复计算的问题
     * 递归的话，就考虑最少的数，条件满足结果就满足，做数学题的关键思路
     */
    public static int maxMoney1(int[] nums, int idx) {
        if (idx < 0 || nums == null || nums.length == 0) {
            return 0;
        }
        if (idx == 0) {
            return nums[0];
        }
        return Math.max(
                //这个是奇数开始
                maxMoney1(nums, idx - 2) + nums[idx],
                //这个是偶数位开始
                maxMoney1(nums, idx - 1));
    }


    /**
     * 数学推导
     * 个数>2
     * result=arr[0]+...要么隔1个要么隔2个
     * result=arr[1]+...要么隔1个要么隔2个
     * 个数=1
     * result=arr[0]
     * 个数=2
     * result=Math.max(arr[0],arr[1])
     */
    public static int maxMoney2Note(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            //数组元素都是>0的
            //0 2 4
            //1 3 5 7
            dp[i] = Math.max(
                    //这个是偶数位开始
                    dp[i - 1],
                    //这个是奇数开始
                    dp[i - 2] + nums[i]);
        }
        return dp[length - 1];
    }


    /**
     * 优化重复计算，先查，没有就计算，再保存
     * 采用备忘录的第一个，第二个一般是自己指定数值
     */
    public static int maxMoney2NoteLevel(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int first = nums[0];// 0 2 4
        int second = nums[1];// 1 3 5
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    // https://leetcode-cn.com/problems/house-robber-ii/
    //todo--------------------首位相连 看成循环链表-------------------------------
    // arr[0]与arr[arr.length-1]相邻
    //
    public static int maxMoney2Level(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], nums[0]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        //偶数的话
        if ((length & 1) != 0) {
            return Math.max(dp[length - 1] - nums[0], dp[length - 1] - nums[length - 1]);
        } else {
            return dp[length - 1];
        }
    }

    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 1};//2,7,9,3,1
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(maxMoney2Level(nums));
    }
}
